package com.itHsuSE.homework;

import java.util.Arrays;

public class HomeWork1_1 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int num = 4;
        //打印插入前的数组
        System.out.println(Arrays.toString(arr));
        //二分查找
        int index = binarySearch(arr, num);
        //创建一个新数组，插入新的值
        int[] newArr = insertElement(arr, num, index);
        //打印插入后的数组
        System.out.println(Arrays.toString(newArr));
    }

    /**
     * 二分查找算法，用于查找目标元素在有序数组中的插入位置
     * @param arr 有序数组
     * @param target 目标元素
     * @return 目标元素在数组中的插入位置
     */
    public static int binarySearch(int[] arr, int target) {
        //定义左右指针
        int left = 0;
        int right = arr.length - 1;
        //当左指针在右指针的右边时则不进入循环
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {//找到了
                return arr[mid];
            } else if (arr[mid] > target) {//在当前mid位置的左边
                //让右指针位于mid的上一个位置
                right = mid - 1;
            } else {//在当前mid位置的右边
                //让左指针位于mid的下一个位置
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 将目标元素插入到有序数组的指定位置
     * @param arr 有序数组
     * @param target 目标元素
     * @param index 插入位置
     * @return 插入后的新数组
     */
    public static int[] insertElement(int[] arr, int target, int index) {
        //创建一个新数组，长度比原数组多1
        int[] newArr = new int[arr.length + 1];
        //先将要插入的元素前的元素插入
        for (int i = 0; i < index; i++) {
            newArr[i] = arr[i];
        }
        //插入要插入的元素
        newArr[index] = target;
        //再将要插入的元素后的元素插入
        for (int i = index + 1; i < newArr.length; i++) {
            newArr[i] = arr[i - 1];
        }
        return newArr;
    }
}
